#include <iostream>
using namespace std;

class Solution
{
  public:
    int lengthOfLIS(vector<int> &nums)
    {
        return dfs(0, MIN_INT, nums);
    }

  private:
    int dfs(int x, int prev, vector<int> &nums)
    {
        if (x >= nums.size())
            return 0;
        int take = 0;
        if (nums[x] > prev) //选
            take = 1 + dfs(x + 1, nums[x], nums);
        int no_take = dfs(x + 1, prev, nums);
        return max(take, no_take);
    }
};

class Solution
{
  public:
    int lengthOfLIS(vector<int> &nums)
    {
        int n = nums.size();
        mem.resize(n, -1);
        int ans = 0;
        for (int i = 0; i < n; i++)
        {
            ans = max(ans, dfs(x, nums));
        }
    }

  private:
    vector<int> mem;
    int dfs(int x, vector<int> &nums)
    {
        if (mem[x] != -1)
            return mem[x];
        if (x >= nums.size())
            return 0;
        int res = 1;
        for (int j = 0; j < i; j++)
        {
            if (nums[i] > nums[j])
                res = max(res, 1 + dfs(x + 1, nums));
        }
        mem[x] = res;
        return res;
    }
};




const int N = 10010;
class Solution
{
    int dfs(int x, vector<int> &nums)
    {
        int res = 1;
        if (mem[x])
            return mem[x];
       for (int i = 0; i < x; i++)
       {
           if (nums[i] < nums[x])
               res = max(res, 1 + dfs(i, nums));
       }
       mem[x] = res;
       return res;
    }
public:
    int mem[N];
    int dp[N];
    int lengthOfLIS(vector<int>& nums)
    {
        int n = nums.size();
        int ans = -1e9;
        for (int i = 0; i < n; i++)
        {
            dp[i] = 1;
            for (int j = 0; j < i; j++)
            {
                if (nums[j] < nums[i])
                dp[i] = max(dp[i], 1 + dp[j]);
            }
        }
        int res = 0;
        for (int i = 0; i < n; i++)
        {
            res = max(res, dp[i]);
        }
        return res;
    }
};




